#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/12/6 13:51
# @USER    : Shengji He
# @File    : PascalTriangle.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        """
        Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

        In Pascal's triangle, each number is the sum of the two numbers directly above it.

        Example:
            Input: 5
            Output:
                [
                     [1],
                    [1,1],
                   [1,2,1],
                  [1,3,3,1],
                 [1,4,6,4,1]
                ]

        :param numRows:
        :return:
        """
        ans = []
        for i in range(numRows):
            row = []
            for j in range(0, i + 1):
                if j == 0 or j == i:
                    row.append(1)
                else:
                    row.append(ans[i - 1][j] + ans[i - 1][j - 1])
            ans.append(row)
        return ans

    def generate2(self, numRows: int) -> List[List[int]]:
        if numRows == 0:
            return []
        ans = [[1]]
        while len(ans) < numRows:
            new_row = [a + b for a, b in zip([0] + ans[-1], ans[-1] + [0])]
            ans.append(new_row)

        return ans


if __name__ == '__main__':
    S = Solution()
    numRows = 5
    print(S.generate(numRows))
    print(S.generate2(numRows))
    print('done')
